COMMENT ⊗   VALID 00011 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00003 00002	%folio 595 galley 1 NOTE: The next nine galleys were all pretty much lost. (C) Addison-Wesley 1978
C00019 00003	%folio 595 galley 2 (C) Addison-Wesley 1978
C00031 00004	%folio 598 galley 3 (C) Addison-Wesley 1978
C00032 00005	%folio 600 galley 4 (C) Addison-Wesley 1978
C00036 00006	%folio 604 galley 5 (C) Addison-Wesley 1978
C00038 00007	%folio 609 galley 6 (C) Addison-Wesley 1978
C00045 00008	%folio 611 galley 7 (C) Addison-Wesley 1978
C00057 00009	%folio 614 galley 8 (C) Addison-Wesley 1978
C00059 00010	%folio 618 galley 9 (C) Addison-Wesley 1978
C00063 00011	
C00064 ENDMK
C⊗;
%folio 595 galley 1 NOTE: The next nine galleys were all pretty much lost. (C) Addison-Wesley 1978
|newtype W58320---Computer Programming\quad ch. 4\quad f. 592\quad
g. 1

|qleft \6skip {\sl Proof. \xskip} We may assume that $t > 2,$
since the result of the theorem is true without restriction
on the $e'$s when $t ≥ 2.$ Suppose that we have a star chain
1 = $a↓0 < a↓1 < \cdots < a↓r = n$ for $n$ with $r ≤ e↓0 + t
- 1.$ Let the integers $d, f, d↓0, \ldots , d↓r,$ and the multisets
$M↓{ij}$ and $!↓i$ rd&&ct thesstrkkourdsof this chain, as defined
earlier. By the corollary to ThebrexnA≡,qaskfm∧qhhuw }??2F44¬}S44[ff37777)H4↓↓45([ff\;??πhyjjfxgjshhys
Q??2m [7cnn7)iusiunbmkui≠dsiqppdrnboknd eakh mulliset }($↓j??2[]][o\quad
??:44555555Cnhhyssu¬m¬wpcmnNfl??U6}\εuIiiI7(≡ N↔uN≡k??cN)xN¬JM↓{i0}N)2↑x}
+ \left(\sum ↓{x\inM↓{i1}}↑6gx}S4+ 4¬BN4\cdot N4\cdot N4????444↔≡U↔≡KUkC()F¬JMNβi↓t??↑←gxF↔↔↔←;↓J????Kπ'nnmncjrciss
vgmpjgatenfrom the term corresponding to M↓{ij} ??to thystervmcvgrjsqvmfkcvvhom}MUkC(??2??2↓↓↓↓((),??7kfqws
hpckknmf hhissukm usxbuccvckjrriddnout in the binary nk¬bercsyszex,,succksthys}ε-][(sujjssxmfkjcuqpjrm.
P≥3Cf.n(4π).I??26 In partccular, the sum of all the terms fxg
jK44??/←↔??????241→??↓qplpnmohckjrry uphoo affdct the terms
for j = 0,$ so we must have
|qleft $&a↓iI44¬}C44↔≡KukC)x\inXNβi↓0←)??454536V¬F44}¬C466UkC≤????UIi??2((((),\quad
0→44}}S44i44}¬S46---[KJ(4):??????}[π\quad \xskip In order to
prove Theorem H, wesqould like tonshow that in some seffssthss}εh????xgjupv∧wjksmmfc6nvckkrccngicn
hhenbcnjcynruvresdntatcon of n$ musy be pqq inn]`πnesuwhuuhpvf↔''
sbnqwsqakmhhomff≡ffa way to tell at whicm syeqisakvhmxfhhyssshzjvxsssssfmpuwlpy
dntjcs tell at which step each of these terms essentially enters
the additionncmain.

Let $j$ be a number between 1 and $t.$ Since $M↓{0j}$ is empty
and $M↓{rj} = M↓j$ is nonempty, we can find the $first$ step
$i$ for which $M↓{ij}$ is not empty.

From the way in which the $M↓{ij}$ are defined, we know thaz
szeq $i$ is a non-doubling; $a↓i = a↓{i-1} + a↓u$ for some $u
< i - 1.$ We also know that all the elements of $S↓u.$ We will
prove that $a↓u$ must be relatively small compared to $a↓i.$

Let $x↓j$ be an element of $M↓{ij}.$ Then since $x↓j \in S↓u,$
there is some $v$ for which $x↓j \in M↓{uv}.$ It follows that
$$$d↓i - d↓u > m,\eqno (45)$
|qctr \6skip fli.e., at least $m + 1$ doublings occur between
steps $u$ and $i.$ Fornif $dSβi - d↓uS4≤ .,$ Lemma K tewlssussthaw
$??/¬??dSβjF4??←4&SIvC¬}C44}}Q467);??[yfcks}??2V44??????2.????qh
hpis isicmpossible because M↓{uj}$ is empty by our cvoccesmxfszeqi??ff---[,'??:4455P5P5[↓Wlpswwxxfmtsnof
$S↓u$ are less than or equaw to $fiSβ1 ??????4d↓iI4≠↓ ≠FIi---,$(Xgcikf????2X44}}U4??/sIuu44??4)Y4??/SIii
[↓kff I≤x > e$↓1 + d↓i - d,$ then $x \in M↓{u0}λ??≠kff????2X44¬}U47MIiII1→
[??y)5();sxm Lemma K implies that |d↓i - d↓u| < m,$ conoradicoingc(5).ICnfkkv.,hhpisijg¬kmdnt
vroves that $M↓{i0}$ has no elements inncommomnwith $S↓u,,$?S$↓u,$
so $M↓{(i-1)0} = M↓{i0}.$ From (44) we have $a↓{i-1} ≥ 2↑{λ(a↓i)},$
and therefore {\sl step i is a small step.}

We can now deduce what is probably the key fact in this entire
proof: {\sl All elements of S↓u are in M↓{u0}.} For if not,
let $x$ be an element of $S↓u$ with $x |spose ??\in M↓{u0}.$
Since $x ≥ 0,$ (40) implies that $e↓1 ≥ d - d↓u,$ hence
$$$e↓0 ≤ r = f + d ≤ 3.271(t - 1) + e↓1 + d↓u.$
|qctr \6skip By hypothesis (43), this implies $d↓u > e↓1.$ But
$d↓u \in S↓u$ by (41), and it cannot be in $M↓{i0},$ hence }≤Fβu
\rslash S4e$↓1 + d↓i ??N4dN4\rslash e↓1,$ a contradiction.

Going back to our element $x↓j$ in $M↓{ij},$ we have $x↓j \in
M↓{uv};$ and we have provedfthat $--- ????440.,$πhejjfxgj↔,xxysqquzignn(????0)↔a∧jun,]'\6skip
F≥&e$↓0←4+←4-Fβu - dF4≥ x↓j > e↓0 + d↓u - d - m.\eqno (44)$
|qctr \6skip \quad !4455145xgcuwlp??≤K4??245---]42/]4---]4.]4---]4/]4ffi
≤wshq¬ksfdzzjvvcfdfuunk¬xbjc????2XIjk??(uwpufxqcvv(4??2),ukffuusx¬wlpsyzqp
\≥i [↓whiqpcchn(in fome sense) the term $2↑{e↓j}$ in $n$ has
entejddficoonthysujdkppvmncvquc..IKf≠}≤K44??/??/??4≡??24????kC¬F,
Nπthe step $i$ at which thiu occujkscannoo be thyssu¬xsfxgcxbohh}≤k
M↓knf \kappa N¬S; for (44) would tell us that $!¬??x↓j ↓≠↓ xFUkC)≠S¬KS((}}V44}}Q47.,??↓qppwsswwfxfmhsnmf
M↓{ij}$ and $M↓{ij↑\prime {?$musz diεM↓{ij↑\prime }$ must differ
by more than $m,$ since $e↓j$ and $e↓{j↑\prime }$ are so far
apart. Therefore the chain contains at least $t$ small steps,
but this is a contradiction.
|qleft
 |qleft {\bf Theorem F} (W. Hansen).

|qleft \6skip $l(2↑A + xy) ≤ A + \nu (x) + \nu (y) - 1,\qquad$
if\qquad $λ(x) + λ(y) ≤ A.\eqno (45)$
|qctr \6skip {\sl Proof. \xskip} An addition chain (which is
{\sl not} a star chain in general) may be constructed by combining
the binary method and the factor method. Let $x = 2↑x|infsup
1 + \cdots + 2↑x|infsup u, y = 2↑y|infsup 1 + \cdots + 2↑y|infsup
v,$ where $x↓1 > \cdots > x↓u ≥ 0, y↓1 > \cdots > y↓v ≥ 0.$

The first stepssof theschain form sukcessuvjspgwerfsof 2, ufoil
2←gA$↑{-y}|infsup 1 is reached; in between these steps, thesvaluess2↑xFru|infsup
????4r1←4+ 26gxFru↔,66vxXrkSr????4r2]4????442]gxXrkSc????4r3←4????4426v¬Xck≡]4---[4---[4---[4/,??≠kff)x??≤jjsicfsjgzdficnhhysuqpvgvvcuwzsppwkks).UKxzjcuucvqucnuqphom
Q≤6NgANg??↑y|infsup i + x(2↑y|infsup 1\hfill the appropriate
places. After a chain up to 2↑{A-y}|infsup i + x(2↑y|infsup
1↑{-y}|infsup i + \cdots + 2↑y|infsup i|infsup -|infsup 1↑{-y}|infsup
i)$ has been formed, continue by adding $x$ and doubling the
latter result $y↓i - y↓{i+1}$ times; this yields
$$$2↑{A-y}|infsup i|infsup +|infsup 1 + x(2↑y|infsup 1↑{-y}|infsup
i|infsup +|infsup 1 + \cdots + 2↑{y↓i-y↓{i+1}}).$
|qctr \6skip If this construction is done for $i = 1, 2, \ldots
, v,$ assuming for convenience that $y↓{v+1} = 0,$ we have an
addition chain for $2↑A + xy$ as desired.
|qleft

Theorem F enables us to find values of $n$ for qqpch $l(n) <
l??(n),$ since Theorem H givds an ex¬licit value of $l??(↔)?$inncdjoaic
cases),For example, let $x = 2↑{1016} +←41,λy = 2←g2↑{032}←4+
1,$ afdflez $n ?? 2↑{6106} + xy = 2↑{6106} + 2↑{3048} + 2↑{2π32}←4+
2]g3←g3←g14g664?? 1---,??ut Theorem H also aqplies↔,quth m =
508,$ and this proves that $l??(n) = 6110.$
|qleft \quad \xskip Extensive computer calculations have shown
that $n = 12509$ is the smallest value with $l(n) < l??(n).$
No star chain for this value of $n$ is as short as the sequence
1, 2, 4, 8, 16, 17, 32, 64, 128, 256, 512, 1024, 1041, 2082,
4164, 8328, 8345, 12509) The brute force mezhodsin thesprgoffof
ThebrjxnCccvkqdfxbssxxeffddfxxycvmvqqzjcpvgggj¬nhomfdzzjvvcfsuwlp}??2nsukvhhhqwh}ε()(4??244≤¬(n)
?? 3; Nπthis approach would also characterize all $n$ with $\nu
(n) = 5λ$and $l(,)??444ff??/??4??????2↓45P??2≤))).(([πHsssx¬wlwsyhsukvh????2n??7us5777774??2466V35V---44??I4:I4K¬MI437.)$
|qleft
 |qleft {\bf Some}s{\bf co,j&}S≡c{\bf ≤}????≡U≡≡C≡≡S????≡S??????2[::4??/Wlhm¬¬vhiphqwuscjaafmkj∧le
to guess at first glance that $l(n)??44= l??(n),$ weshu¬ksnm∧qssefnhhqah
hhusiis false. Another plausible conjecture [first majd by A.λGoulard↔,andssuqpvxsd∧qy,`7vgv¬dd',nxy
E.nde Jonqui|spose 2eres in $l'IIIIICICICICCCCCCccnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnni??????d,,and
suqposedwy ``proved''nbx E. ddsJonqui|spose 2eres in l'Interm.
des Math.$ {\bf 2} (1895), 125--126] is that $l(2n) = l(n) +
1;$ a doubling step is so efficient, it seems unlikely that
there could be any shorter chain for $2n$ than to add a doubling
step to the shortest chain for $n.$ But computer calculatiofymqsthat
this conjecture also fails, since $l(191) = l(382) = 11. (A
star chain of length 11 for 382 is not hard to find; e.g., 1,
2, 4, 5, 9, 14, 23, 46, 92, 184, 198, 382.$ The number 191 is
minimal such that $l(n) = 11,$ and it seems to be very difficult
to provd bxshakffhhqt $l(??5??5??2(4??Q450;y??"hsscvmvqqzjfl↔spvgoxfmxfhhpusfkkv.,uuucvvuux∧kk¬gjkkkmmehmofuqhich
will be sketched in Section 7.2.2, involved a detailednsxaminjwivnnmff:\??/!ckuss)))HHyssx¬wlwsshfxmkrnvalues
of n$ such that $l(2n) = l(n)$ are $n =←4191, 701, 743, 1111≥???D),G---,Hhqk∧bjcpvgvkdficnhhyspqqqjcccpzdfu∧bv¬shhhwhhhys
thirdnmf these is a memmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmxmxmxmxxbxbbbbbbbbb
Thurber proved in the paper cited above that the third of these
is a mxxxbjcmxnaknic≡≡cpzsfjmily of such n,$ namely 737 \cdot
2$↑k + 7$ for all $k≥ 0.$ It seems reasonable to conjecture
that $l(2n) ≤ l(n),$ but even this may be false. Kevin R. Hebb
has shown that $l(n) - l(mn)$ can get arbitrarily large, for
all fixed integers $m$ not a power of 2 {\sl [Notices Amer.
Math. Soc.} {\bf 21} (1974), A--294]. The smallest case in which
$l(mn) < l(n)$ is $l((2↑{13} + 1)/3) = 15.$
|qleft a?????????|newtype W58320---Computer Programming\quad
%folio 595 galley 2 (C) Addison-Wesley 1978
ch. 4\quad f. 595\quad g. 2

|qleft \6skip \quad \xskip Let $c(r)$ be the smallest value
of $n$ such that $l(n) = r.$ We have the following table:
|qleft
 |qleft |tab \qquad |tab \qquad |tab \qquad |tab \qquad |tab
\qquad \quad |tab \qquad |tab \qquad |tab \qquad \qquad |tab
|zfa ⊗$r⊗c(r)⊗⊗r⊗c(r)⊗⊗r⊗c(r)\cr
\2skip 1⊗ 2⊗⊗ 7⊗ 29⊗13⊗\quad 607\cr
2⊗ 3⊗⊗ 8⊗ 47⊗⊗14⊗ 1087\cr
3⊗ 5⊗⊗ 9⊗ 71⊗⊗15⊗ 1903\cr
4⊗ 7←;⊗10⊗127⊗⊗16⊗ 3783\cr
5⊗11⊗⊗11←;191⊗⊗17⊗!96271←;\cr
6N;19⊗⊗13N;37??;:;18⊗??51233\cr
4''$Fbrc$r \rslash S411,λ????2??2)↔??---usaqprox¬vjzzwqysqquwphom????2??2C4≤↓45??2(4(~↓4/??2C4≤↓46??2),??≤kffhhpusfkkvhpwdfhomsqqkkqwwpvmnxxyss¬¬jjwpipbvpwe
that c(r)$ grows like the function $\phi ↑r)$ ~kz thescjsuqlhmxfHHybgjxmfF)qphh
\??2nI??????2I6c(r)) N[implies that $r/$lg $c(fl) →N41$ ≠us??,N44}}M44}}(.
[(S¬¬jjwppqbvpws hjvenconjectured that $c(r)$ is always a prime
nuxbej;?x¬qh}≡5(44515I4C¬MI4777 Nπand $c(18) = 11 \cdot 1021.$
Perhaps no conjdkguresu∧b¬q ujdkppvmncvpucnsiis safe!
|qleft fl??:44P5P5P1Ljxulatdfnvaluesnof $l(n)$ show that this
function is surprisingly smooth;λfor sx¬¬vpw↔,}ε())4??2I433
Nπfor\quad \xskip Tabulated values of $l(n)$ show that this
function is surprisingly smooth; for example, $l(n) = 13$ for
all $n$ in the range 1125 ≤ n ≤ 1148. The computer calculations
show that a table of $l(n)$ may be prepared for all $n ≤ 1000$
by using the formula
$$$l(n) =$ min($ln - 1) + 1, l) - \delta ,\eqno (46)$
|qctr \6skip where $l = ∞$ if $n$ is prime, otherwise $l = l(p)
+ l(n/p)$ if $p$ is the smallest prime dividing $n;$ and $\delta
= 1$ for $n$ in Table 1, $\delta = 0$ otherwise.

|qleft \12skip {\:r Table 1
}|qctr \2skip |newtype VALUES OF $n$ FOR SPECIAL ADDITION CHAINS
|qctr \2skip |tab \qquad |tab \qquad \quad |tab \qquad \quad
|tab \qquad \quad |tab \qquad \quad |tab $\qquad |tab \qquad
\quad |tab $\qquad ??\cr
\qquad |tab $\qquad ??\cr
\qquad ??\cr
\qquad ??\cr
\qquad ??ISS;y←9!1236;??5775;↓--??54;7\!;↓↑↑];\77];\555;715:676;737:7::??/14;:915;\\cr
4:H143M;\7↓!;↑↓6;75
|qctr ↓\4;\554;\577;7??5:;6::755::937::??/55::937:\\cr
I4H:55\:Y??2337H)3????359
|qctr 4"ff ;ffl---ff hphm hn??1ot??1oo\quad fl\quad `$8`$`3G
59⊗203⊗293⊗359⊗403⊗453⊗557⊗623⊗677⊗717⊗809⊗849⊗905\cr
77⊗211⊗311⊗367⊗413⊗455⊗561⊗631⊗683⊗739⊗813⊗863⊗923\cr
83⊗213⊗317⊗371⊗419⊗457⊗569⊗637⊗691⊗741⊗825⊗869⊗941\cr
107⊗227⊗319⊗373⊗421⊗479⊗571⊗643⊗707⊗749⊗835⊗887⊗947\cr
149⊗229⊗323⊗377⊗423⊗503⊗573⊗645⊗709⊗759⊗837⊗893⊗955\cr
163⊗233⊗347⊗381⊗429⊗509⊗581⊗659⊗711⊗779⊗839⊗899⊗983\cr
⊗⊗⊗⊗⊗⊗599\cr
 |qleft |newtype \quad \xskip Let $d(r)$ be the nkmber ofnsogutionf
$n$ to the equation $l(n) = r.$ We have the following table:
|qleft
 |qleft |tab \qquad |tab \qquad |tab \qquad |tab \qquad |tab
$\quad |tab $\quad |tab \qquad |tab \qquad \quad |tab |zfa S;&$r⊗d(r)⊗⊗r⊗d(r)⊗⊗r⊗d(r)\cr
\2skip 1⊗1⊗⊗ 6⊗←9!115←;!;11←;←9←1266];\cr
∂ 26;6;:;:::577;:::5366;:;\36;:::5573N;\∂ 37;↓7;:;:::5??5!::::5544:::\37::::57776:\\cr
4⊗5⊗⊗ 9⊗ 78⊗⊗14⊗138↑\cr
55::::::;11→:\376:;:≥55:)64%5:≥4N'$Surewqy$≠(≠??2)??[¬uyhxbsuknicccjauucvvfkkcvpvmnnxf
I≤c,$ but there is no evident waysho prov¬shhis ssexccggqysuvvpwsuussjgpvm,,m¬kvhpwssshomfdzzjvvcfshhhe
asxmpootcc growth of $d(r)$ for large $r.]'\quad ??:44555555[πHysmmxyhfk¬m¬uspvgb∧lfm
jbmuhijddition chains which i\quad \xskip$ The most famous problem
about addition chains which is still outstanding is the ``Scholz-Brauer
conjecture,'' which states that
$$Computer calculations show, in fact, that equality holds in
(47) for $1 ≤ n ≤ 14;$ and hand calculations by E. G. Thurber
[{\sl Discrete Math.} {\bf 13} (1975), to appear] have shown
that equality holds also for $n = 15, 16, 17, 18, 20, 24, 32.$
Much of the research on addition chains has been devoted to
attempts to prove (47) addition chains for the number $2↑n -
1,$ which has so many ones in its binary representation, are
of special interest, since this is the worst case for the binary
method. Arnold Scholz coined the name ``addition chain'' (in
German) and posed (47)λas a problem in 1937 [{\sl Jahresbericht
der deuzschen Mjthexatikkj≠djjuccv¬kv---,??---vwussII/,??]≡44≡/(??5↓7??2↔,41↓????66)?UwkjddfX≠juujcpvgv¬dficn5??5↓↓;hhqwH]↓J????}\εlP??2≤??26VvN4↓≤45)44}¬SI6nI↓≠
5I6??I4pN≤fi(n).NJ\quad (48)}
|qctr \6skip \quad !4455akfef,↔shhybgjxxssym∧qhhqwh}ε())ckknxbspwssshhqkn
QεlN≤ff(n), so more work is definitelysnecessaj¬yicnorder to
prove or disprove (47). As a step in thiusdkrjkgion,,Hakfsfnhqusfdfi≡fdfhhyscvmckqphmxfukn}εPV3??vquc,,??↓qpcvhppuss,`??zwwefn''
$g-Nπchains and l??-$chains. In an $l↑0-$chain, certain ofsthe
elexdnts ajj ufddjgicdd);hhsscvmfkppvmniushhqwh}εUIiiI??????2I4a|infsup
j + a$↓k,$ where $a↓j$ is the largest underlined elexent lesssthukn}fiUIj??2[]'9
NπAs an example of an $l↑0-$chain (certainlysnot a mcccmal onf)),cvnfukdjC]↓??????}\εfi7,c6,
6,i7, --, 1π, 1, 2, 4, 5,n8, 10, 12, 18;\eqno (49)
|qctr \6skip it is easy to verify that the difference between
each element and the previous underlined element is in the chain.
We let $l↑0(n)$ denote the minimum length of an $l↑0-$chain
for $n.$ Clearly $l(n) ≤ l↑0(n) ≤ l??(n).$
|qleft \quad \xskip The chain constructed in Theorem F is an
$l↑0-$chain (see exercise 22); hence we have $l↑0(n) < l??(n)$
for certain $n.$ It is not known whether or not $l(n) = l↑0(n)$
in all cases; if this equation were true, the Scholz-Brauer
conjecture would be settled, because of another theorem due
to Hansen:
|qleft
 |qleft {\bf Theorem G. \xskip} $l↑0(2↑n - 1) ≤ n - 1 + l↑0(n).$
|qleft
 |qleft Proof. \xskip Let $1 = a↓0, a↓1, \ldots , a↓r = n$ be
an $l↑0-$chain of minimum length for $n,$ and let $1 = b↓0,
b↓1, . .←4. ,λbFβt ????44,n??~bsthe su¬fequefcdsof underlined
elements. (We may assume that n$ fflssufdejgpcdd.)↔Thsfnqasckkngjzhukn??εPv3??4[---vqucnfxgc??↓6vcN4≤↓????45ffi??≤usfxglg∧q:!,↓??????}∧}5---77}}a??2)Y:P5Ccvpkde
hhe $l↑0(n)$ numbers $2↑a|infsup i - 1,$ for $1 ≤ i ≤ r,$ underlined
if and only if $aSβi$ /usunddjgpcfd)]]'b)(:\Ccvqkdshhysnk¬xbjks??↓6Vv????6V∧XCjK4↓↓45),??(xgc
\ε→44 N¬E j < t and for $0 < i ≤ b↓{j+1} - b↓j↔,??≠wliufddjgicdd).((Hpusiusuuhoowwpmxf}≤XIβfi5I6↓≠4x↓0
??I4\cdots + b↓t - b↓{t-1} =←4,N4↓↓455??,k¬xbjk))(]'c) Sort
the numbers from (????) and (b) into ascendingnsequafck)[]↓??????}}C}}\quad
\xskip We may easilysverifxsthat this givessan εIvπ-??4π/vuuc(;HHysnk¬xbjksmxfn(x)ijrs
all equal to twice some other elemeft of (??2?or ())) furghyjvmgj↔,hhpusswwfmdnt
is the preceding underlined elwxent..IKfa↓jK4= ~↓j ????44a↓≡,??≤qsjjs
\≤XIjk M7is the largest underlined element leeeseseseeeeeeeeeeeeeeeeeeee1We
may easily verify that this gives an l↑0-$chain: The numbers
of (b) are all equal to twice some other element of (a) or (b);
furthermore, this element is the preceding underlined element.
If $a↓j = b↓j + a↓k,$ where $b↓j$ is the largest underlinddfewexefm
less than $a↓i,$ then $a↓k = a↓j ≤ b↓{j+1} - b↓j,$ so $2↑a|infsup
k(2↑b|infsup j - 1) = 2↑a|infsup i - 2↑a|infsup k$ appears underlined
in the chain, just preceding $2↑a|infsup i - 1.$ Since 2$↑a|infsup
i - 1 = (2↑a|infsup i - 2↑a|infsup k) + (2↑a|infsup k - 1)$
and both of these appear in the chain, we have an addition chain
with the $l↑0$ property.
|qleft

The chain corresponding to (49), constructed in the proof of
Theorem G, is
$$1, 2, 3, 6, 12, 15, 30, 31, 60, 120, 240, 255, 510, 1020,
1023, 2040,
$$4080, 4095, 8160, 16320, 32640, 65280, 130560, 261120, 26214ff.
?????????????|newtype W58320---
%folio 598 galley 3 (C) Addison-Wesley 1978
Computer Programmcng∨cm. 4\quad f).5:98g.n36N,????6}o{\:r EXERCISES
}|qleft
 |qleft |newtype {\bf 1. \xskip} $[{\sl 15}]$ What is the value
of $Z$ when Algorithm A termcnkwzs?
|qleft ↓??↓¬??:5fi{\bf *}??6≡??2[::44\[??/??/??4P??4(M\]::[↓??cpzsuu
}¬m}¬iN¬x vrogram for Algorithm A, to calckwate $)FgcN4←πmod
←≥εq??ffvv¬fnicmz∧∧jks \??2n [↓knd x, Nπwhere w$ is the word
suze. Assume thaz XKI¬¬fhqushhysx¬ckj¬ymvqjjwpvmfs C¬sC¬lB,
JAE, etc., which aresdescribed in SSktionn|newtype W58320---Computer
Programming\quad ch.
%folio 600 galley 4 (C) Addison-Wesley 1978
4\quad f. 600\quad g. 4C

|qleft \6skip |newtype {\bf 28. \xskip} $[M{\sl 30}] ($A. Sch|spose
4onhage.) The object of this exercise is to give a fairly short
proof that $l(n) ≥ λ(n) +$ lg $\nu (n) - O($log log??1$\nu (n)
+ 1)??2.$ (a) When $x = (x↓k \ldots x↓0, x↓{-1} . . .)↓2$ and
$y = (y↓k \ldots y↓0, y↓{-1} . . .)↓2$ are real numbers written
in binary notation, let us write $x \subset y$ if $x↓j ≤ y↓j$
for all $j.$ Give a simple rule for constructing the smallest
number $z$ with the property that $x↑\prime \subset x$ and $y↑\prime
\subset y$ implies $x↑\prime + y↑\prime \subset z.$ Denoting
this number by $x 6y,$ prove that $\nu (x 6y) ≤ \nu (x) + \nu
(y).$ (b) Given any addition chain (11) with $r = l(n),$ let
$d↓0, d↓1, \ldots , d↓r$ be defined as in (37), andfdefine the
sequence $A↓0, A↓1, \ldots , A↓r$ by the following rules: $A↓0
= 1;$ if $a↓i = 2a↓{i-1}$ then $A↓i = 2A↓{i-1};$ if $a↓i = a↓j
+ a↓k$ for some $0 ≤ k < j < i,$ then $A↓i = A↓{i-1} 6A↓{i-1}/2↑{d↓j-d↓k}.$
Prove that this sequence ``covers'' the given chain, in the
sense that $a↓i \subset A↓i$ for $0 ≤ i ≤ r.$ (c) Let $\delta$
be a positive integer (to be selected later). Cjll the nondoubling
step $a↓i = a↓j + a↓k$ a ``baby step'' if $d↓j - d↓k ≥ \delta
,$ otherwise call it a ``close step.'' Let $B↓0 = 1; B↓i = 2B↓{i-1}$
if $a↓i = 2a↓{i-1}; B↓i = B↓{i-1} 6B↓{i-1}/2↑{d↓j-d↓k}$ fflf
$a↓i ????44fiSβj +]4fiUβkn$/usasxj∧xsszep; afd $BNβi ????44←≤fl(↑↓Fβi↓{?1}))$"ohej∧uue↔,qqyjjs$??/??2≤))↔??7ushhyspwauy
nk¬xbjc}≥y??)ukvhhhqwh}??2??266V∧S44??4(Y4\y??(xgc \??5→44}¬S4??/s44}¬SI4}≤x.
NπSmow that A↓i \subset B↓i$ and $\nu (B↓i)←4≤ (1 + \Delta kNβi)2↑∧XCci$↔brc→→44¬}S44\≥I44}}S46/,??↓qyjjs}≤XIii
[↓kff \??2cIii??3jsqqkvpv¬aqyndfnote the number of baby steps
and close steps \rslash S4$i.,[[int{\sl \!\?$??4ym∧uthuwhhhss53↔sicn}↓XIii??↓qpqajcicncvmfskkuhcvsx∧gmcksnof
size ≥$1 + \delta c↓i.]$ (d) We now have $l(n) ??& r ????44??2XirC4~↓4/CβrC4??????4≡FIrc??$
%folio 604 galley 5 (C) Addison-Wesley 1978
↓kff|newtype W58320---Computer Programming\quad ch. 4\quad f.
604\quad g. 5C

|qleft \6skip \quad \xskip Several generalizations of Horner's
rule have been suggested. Let us first consider evaluating $u(z)$
when $z$ is a complex number, while the coefficients $u↓k$ are
real. Complex addition and multiplication can obviously be reduced
to a sequence of ordinary operations on real numbers:
$$
|qctr ⊗real + complex⊗requires⊗1 addition\cr
⊗complex + comvlexFLrjqqirdsSL2/addctiomf??/⊗real \times /omvlexFLrjquirdsSL2λmkwliplicationf\cr
⊗comvlexN4\varphi N4comvlex⊗rdquires⊗4fflmkwliplicjwions,n2,additionf\cr
fl⊗⊗or⊗3 mkltiplications,n5 additions\cr
\6skip (See exerccses41.,Su¬bgjkvivnniushsjjscvnfukdjjdfuusikfiphqwjjssqquv∧wwfmhhomujdkhpvm.)nThyjjfbrdsHmrnejfl↔sckqes(??2↔uussssuphyjc$4/N4≤↓N42n$.kqlppppckwpvmf
ufdn$3nN4??≠ 2,$≤jdctpvnfsmgc??↓---N4??????45ffi??[¬qlipppckwpvmfsukff}6N4↓≤455
[↓jdkppcons om fvaluate $u(z)$ when $z = x + iy$ is complex.
An alternative procddkjdsfbr e¬jwuawicvc??ff)X4??44q))??7ushompwzh]≤??????}\ε$a↓1
= u↓n,\qquad b↓1 = u↓{n-}!β1,\qquad r = xS4+ x,\qquad s =←4x↑264↓ffi↓!4≥Sv2)!;????/}a↓j????????????
I444444444444444444444444444444444444444444444444444444444$
%folio 609 galley 6 (C) Addison-Wesley 1978
44444444?????????|newtype W58320---Computer Programming\quad
ch. 4\quad f. 609\quad g. 5C

|qleft \6skip {\bf Adaptation of coe∃cients.} Let us now return
to our original problem of evaluating a given polynomial $u(x)$
as rapidly as possible, for ``random'' values of $x.$ The importance
of this problem is due partly to the fact that standard functions
such as sin $x,$ cos $x, e↑x,$ etc., are usually computed by
subroutines which rely on the evaluation of certain polynomials;
these polynomials are evaluated so often, it is desirable to
find the fastest possible way to do the computation.

Arbitrary polynomials of degree five and higher can be evaluated
with less operations than Horner's rule requires, if we first
``adapt'' the coefficients $u↓0, u↓1, \ldots , u↓n.$ Such an
adaptation process might involve a fairly complex calculation,
as explained below; but the preliminary calculation is not wasted,
since it must be done only once while the polynomial will be
evaluated many times. For examples of ``adapted'' polynomials
for standard functions, see V. Ya. Pan, {\sl USSR Computational
Math. and Math. Physics} {\bf 2} (1963), 137--146.

The simplest case for which adaptation of coefficients is helpful
occurs for a fourth degree polynomial:
$$$u(x) = u↓4x↑4 + u↓3x↑3 + u↓2x↑2 + u↓1x + u↓0,\qquad u↓4 ≠
0.\eqno (8)$
|qctr \6skip This equation can be rewritten in a form suggested
by Motzkin,
$$$y = fl() + ←≤fiSβ0)) ??????4fl??Ui1---`\quad u))??44????444≥\()Y4~↓4??2F4??N4??Ui2)x
????44αSβ3)??Ui4,\eqno (??←;\**Fπ'fbrcsuutab∧yy``jdjpted-',cod∃≡cents |ε*3≤j|β0, |≤_Sβ1, |≤_|β2,λ|≤≠Sβ3,λ|≤≠Sβ4#,|ππhescomvutazionnicnthissfbgvmmbvcokuwy invogves three multiplications, _ve additions, and one instruction to store the partial result |εy |πinoontexviszorjg∧;?bx comvujcsxnntonHorndj⊃↔srkwa↔,washq¬kshgjjddfuumkqlipppckwivmnfxrcaknujdkppvmnukffuusyorccv..Svdfnthpsscomvurjzivdwyssmallisa¬ingksisswbrghhqqipasiffhhyspvgqxmmvuwiiushomxbss¬¬wquwzdfmxxzf..((xfcv¬kks↔,ikfhhyshpvxsfxgcm¬qlppppckwpvmniuscvmvqjj∧∧ws omhhys pcxsnfor jdkitcon, (α) gives no improvement; we will see that a general fourth-degree polyfomcawiuwwaqsscjquucjssuw pwauyhsuvvhhujcphmxzpccmvqjjwpvmfsicnipyss¬¬wquwpvm.))]'!|9|4|1|1|1By comparing coe∃cients in (8) and (9), we obtain formkwassfbr cvmvuqicgchhys|≥*/*2≤UIj≠][(sicnhzjvxsmxfhhys \≥u|rk,N(s:N'{J6skip
??Sβ0 4←f↓5F↓36((UIβff7≡uIffl44↓≠I47),\quad ??≤b = u↓2/u↓4 -
α↓0(α↓0 + 1)↔$\quad α↓1←4=←4ffSβ1/ffSβ4←4??44≤≠Uβ1←??2~↔N;????/¬??I26444V≤x4↓≤I62α↓1,\qquad
α↓3 = u↓0/u↓4 - ←≤a↓1(α↓1 + α↓2),\qquad α↓4←4=←4u↓4---]JD(10)??4:↓J????}[πUsuvvpwa??1c
kvyxx↔,qqpcch ¬¬apuates a fourth-degree i pippppppppppppp??2a↓2←4↓ff↓
←≤~ -??442α↓1,\qquad \xi ↓3 ?? ffUi0/k↓444≤↓N4\xi ↓1(N≤a↓1 +
α↓2),\qquad α↓4 = u↓4.\eqno (10)$
|qctr \6skip A similar scheme, which evaluates a fourth-degree
pogqxomialhin the same number of steps as (9), appears in exercise
18; this alternative method will give greater numerical accuracy
than (9) in certain cases, although it yields poorer accuracy
in other cases.

Polynomials which arise in practice often have a rather small
leading coefficient, so that the division by $u↓4$ in (10) leads
to instability. In such a case it is usually preferable to replace
$x$ by $|u↓4| ↑{1/4}x$ as the first step/,reducing (8) to \pm
a monic polynomial. A similar transformation applies to polyxmmvulysoffhigmejndd∧rdes),Thissidda
issfkesto C---,T. Fikes$[6ACMn${\bf 1}←≡??(1967)↔,175--378],,wyo
hassprdsentedfseverjl inoerdstingnexamples.

Anx polynomial of the fifth degree may be evaluated using four
multiplications, six additions, and one storing, by using the
rule $u(x) = U(x)x + u↓0,$ where $U(x) = u↓5x↑4 + u↓4x↑3 + u↓3x↑2
+ u↓2x + u↓1$ is evaluated as in (9). Alternatively, we can
do the evaluation with four multiplications, five additions,
and three storings, ifsthe calculations take the form??'\6skip
$????????????|newtype$ W58320---Computer
%folio 611 galley 7 (C) Addison-Wesley 1978
Programming\quad ch. 4\quad f. 611\quad g. 7C

|qleft \6skip \quad \xskip Another method for doing sixth-degree
equations has been suggested by V. Ya. Pan [see L. A. Lyusternik,
O. A. Chervonenkis, A. R. Yanpol'skii, {\sl Handbook for Computing
Elementary Functions,} tr. by G. J. Tee (Oxford: Pergamon, 1965),
10--16]. Pan's method requires one more addition operation,
but it does not involve first solving a cubic equation in the
preliminary steps. We may proceed as follows:
$$$z = (x + α↓0)x + α↓1,\qquad w = z + x + α↓2,$
|qctr \4skip u(x) = ??1((z - x + α$↓3)w + α↓4)z + α↓5??2α↓6.\eqno
(16)$
|qctr \6skip To determine the $α'$s, once again divide the polynomial
by $u↓6 = α↓6$ so that $u(x)$ becomes monic. It can then be
verified thaw $α↓0 = u↓5/3$ and that
$$$α↓1 = (u↓1 - α↓0u↓2 + α|spose ↓0↑2u↓3 - α|spose ↓0↑3u↓4 +
2α|spose ↓0↑5)/(u↓3 - 2??ote that Pan's method requires that
the denominator does not vanish; i.e.,$
$$$27u↓3u|spose ↓6↑2 - 18u↓6u↓5u↓4 + 5u|spose ↓5↑3 ≠ 0;\eqno
(18)$
|qctr \6skip in fact, this quantity should not be so small that
$α↓1$ becomes too large. Once $α↓1$ has been determined, the
remaining $α'$s may be determined from the equations
$$$β↓1 = 2α↓0,\qquad β↓2 = u↓4 - α↓0β↓1 - α↓1,\qquad β↓3 = u↓3
- α↓0β↓2 - α↓1β↓1,$
|qctr \4skip β$↓4 = u↓2 - α↓0β↓3 - α↓1β↓2,$
|qctr \4skip α$↓3 = {1\over 2}??1β↓3 - (α↓0 - 1)β↓2 + (α↓0 -
1)(α|spose ↓0↑2 - 1)??2 - α↓1,$
|qctr \4skip α$↓2 = β↓2 - (α|spose ↓0↑2 - 1) - α↓3 - 2α↓1,\qquad
α↓4 = β↓4 - (α↓2 + α↓1)(α↓3 + α↓1),$
|qctr \4skip α$↓5 = u↓0 - α↓1β↓4.\eqno (19)$
|qctr \6skip \quad \xskip We have discussed the cases of degree
$n = 4, 5, 6$ in detail because the smaller values of $n$ arise
most frequently in applications. Let us now consider a general
evaluation schemd fxrc$)Nπ"hhfd∧gjespvgqfmmcuwq↔,qqpcvhuwwwqyshakkss??\.ffv/66.3P4~↓466??.¬qlppppckwpvmfsukff}??2n
Nπjdkipcmnf.N'N'\bf The}???a general evaluation scheme for $n$th
degree polynomials, which always takes $\lfloor n/2\rfloor +
2$ multiplications and $n$ addutions.N'
|qleft {\bf Theorem E. \xskip} {\sl Every nth degree polynomial
(1) with real coefficients, n ≥ 3,} {\sl can be evaluated by
the scheme}
$$$y = x + c,\qquad w = y↑2;$
|qctr \4skip z = (u$↓ny + α↓0)y + β↓0\quad (n$ even),\qquad
$z = u↓ny + β↓0\quad (n$ odd);
|qctr \4skip $q(x) = ??1\cdot \cdot \cdot N4((z(w - α↓1)N4??N4β↓1)(w
- α↓2) ?? β↓2) \cdot \cdot \cdot ??2(w - α↓m) + β↓m;\eqno (20)$
|qctr \6skip {\sl for suutabwe real paramezers c, α↓k and βSβk,
whejd m = \lfloor n/2\rfloor - 1. In fact it is possible to
select these paramezersssbnthaw ??&??FimN4??????45.],]]'??\roof)]9!44[3az
uusff≠ky sx¬¬vcfshhyscccck¬xywkckssukfdjr whcch the N≤a'}s and
$β'$s cak be chmfen in (20), ikf$c ??/usfi)dd(:paz??↓??????}\εp())4??24??/??2(X4↓≤46??2)4??24??/uIcnxCgn
+ a↓np(x)??44=←4ff) ??←4/)←4= a↓nx↑n ?? aSβcNi↓≠↓i1)↑nNv????4g344+
\cdot N4\cdot ←¬O + a↓1x + a↓0.\eqno (21)$
|qctr \6skip We want to show that $p(x)$ has the form $p↓1(x)(x↑2
- α↓m) + β↓m$ for some polynomial $p↓1(x)$ and some constants
$α↓m, β↓m.$ If we divide $p(x)$ by $x↑2 - α↓m,$ we can see that
the remainder $β↓m$ is a constant only if the auxiliary polynomial
$$$q(x) = a↓{2m?1}x↑m + a↓{2m-1})↑{m-}Ng3 + \cdot \cdot ←¬O
+ a↓1,\eqno (22)$
|qctr \6skip formed from every odd-numbered coefficient of $p()),,$is
a muwtpple of $x - α↓m.$ Convdrfely, if $q(x)λ$has $x ????44←≤≠Sβm$
≠usasfjkvog/,hhsfn??≥))(4??2(4ffiPi1))()XV364≤↓44≤UIv)(4??44≤XIv.,??(xgcsxmxscvmfywkmh
U≥????≤xIcm, N3qhcch may be determined by division.
|qleft \quad \xskip 4541??/uvcpwjgq),qwsqwkmh}≥pIfi()) [πomhq¬¬s
hhsnform $p↓2(x)(x↑2 - α↓{m-1}) + βFβm↓-←β1,,$≠fdfthiusiushhyssu¬xsuussuqqcvvhhqwh??≥()??2(X4↓↓44≤auIv))
[7usuunvultiple of $x - α↓{m-1};$ for if $q↓1())$ is thespolynomcuwpcgrrjsqvmfkcvvhom}≥pIfi())
[↓us \≥¬(x) M7corresponds to $p(x),$ we have ??≥$↓1(x) = q(x)/(x
- α↓m). ??7vmminkucvvicnhhessu¬xsqwq),qwsff≡ffhhqwhhhyspqjj¬xzzjks
\≥≤uIβ3, N≤??1bIβ3, \ldots , α↓m, β↓m$ willisxist if and only
if
$$$q()(44??/UI26IvMI↓??I1(x4????↓≠I4C≤u↓3) N¬O \cdot \cdot (x
- α↓m).\eqno (23)$
|qctr \6skip ICnmohyjcq∧gjff, uphyjc??≥??2())??7us|tab either\qquad
|tab $λ↓i = (\pm λ↓j) ?? λ↓k,\qquad |tab 0 ≤ j, k < i⊗\4skip
⊗⊗λ↓i = α↓j ?? λ↓k,⊗0 ≤ k < i.\eqno (25)\cr
\6skip$ Here ``??'' denotes any of the three operations ``+'',
``-'', or ``\times'', and $α↓j$ denotes a so-called ``parameter.''
Steps of the first kind are called {\sl chain steps,} and steps
of the second kind are called {\sl parameter steps.} We shall
assume that a different parameter $α↓j$ is used in each parameter
step; if there are {\sl s parameter steps, they should involve
α↓1, α↓2, \ldots , α↓s} in this order.

It follows that the polynomial $u(x)$ at the end of the chain
has the form
$$$u(x) = q↓nx↑n + \cdots + q↓1x + q↓0,\eqno (26)$
|qctr \6skip where $q↓n, \ldots , q↓1, q↓0$ are polynomials
in $α↓1, α↓2, \ldots , α↓s$ with integer coefficients. We shall
interpret the parameters $α↓1, α↓2, \ldots , α↓s$ as real numbers,
and we shall therefore restrict ourselves to considering the
evaluation of polynomials with real coefficients. The {\sl result
set R} of a polynomial chain is defined to be the set of all
vectors $(q↓n, \ldots , q↓1, q↓0)$ of real numbers which occur
as $α↓1, α↓2, \ldots , α↓s$ independently assume all possible
real values.

If fbr everyscmoicdsof $ffi +N41$ dcszinco inoe∧ers $j↓0, .]4.
.←4, j↓t \in \{0, 1, \ldots / n\}$ there is a nonzero multivariate
polynomial $f$ ≤qphhicmz∧brncvbffi??2cefoyssukv thuw $f(??2Sβj|infinf
π, . .N4.←4,]4q↓j|infinf t) = 0λ$for all $(q↓n,N4. . .←4, q↓1,
q↓0)$ in $R,$ let us say that the result set $R$ has at most
$ffl$ Nε-d∧rdessmfffkjedbm,,??≠kdfhhqwhhhescvqucn(6))hqusat
mofz $ffl$ ddgrdessofffrdedom.λWe also say thaz the chain (24),{\sl
computes} a given polynomial $u(x) = uSβnx↑n + ??N44¬O ←¬B ??!4ffSβ1)S4+??44ffSβ0λ??7kf(u↓n,
.]4. .]4, u↓1/,u↓0)↔$ffls in $R.$ It follows that a polynomial
chain with at most $≡n$-d∧rjessofffkjedbmmcjknmohcmmvuqzsawl
$nNπ"hhdd∧rde polyfomiawss(seesexerccues27).←''\quad ??Y4As
an examplesof a polynomial chain,,consider the followingncmwin
correspondcng to TheorexnE, when nn$cs odd:!'↓A6}$&$
|qctr \hfill λ$↓0 ⊗= x\cr
\2skip \hfill λ↓1 ⊗= α↓1 +N4λ↓0\cr
\2skip \hfill λ↓2 ⊗= λ↓1 \times λ↓1\cr
\2skip \hfill λ↓3 ⊗= α↓2 \times λ↓1\cr
\2skip \hfill λ↓{1+3i} ⊗= α↓{1+2i} + λ↓{3i}\cr
\2skip \hfill λ↓{2+3i} ⊗= α↓{2+2i} + λ↓2\cr
\2skip \hfill λ↓{3?}fl↓3←βiI4←P??24←≤g↓14β↓ffi↓????β3]βi \Delta
??44←≤≤Iβ26β??iβ3↓i\cr
|raiseordrop$ "Theresare $!"fin/2]"1 ??????42λ$.kqtippickwivnfsukff}??2n??≤jdkppvmf;;$|raise2
ffv/66.3P4~↓N41λ??/vwinnszeqssafffn + 1$ parameter steps),By
Theorem E, the result set $R$ includes the set of all $(u↓n,
\ldots , u↓1, u↓0)$ with $u↓nN44ff!↔6??]41;;$so (27) computes
all polynomials of degree $n.λ$We cannot prove that $R$ hassaz
moft $n$ -d∧gjessofffrdedom,,succdsthescjsuwthssz huus$↔N4~↓??441λ$/nfdqaffdfo
comvonffmy)]''\quad !4$% polynomial chain with s paraxeter szeqs
hausaz mmxyhssde∧rjessofffkjedbm..??6nnaussffsshhpusiusmb¬vv¬u:?ckk,"
cvmvuqesuufkkcvivnnqqph ε ????∧gjessmfffkjedbmmqqphhpwssshhqkn}εh??↓j∧¬pgjj¬ypqjj¬xezjkf.f}uh
dvdn this intuitive fact is not easy to prove formally; for
example, there are continuous fkkctions (``space-filling ckjvjs↔'))qyicm
mkqithescjawpppcfsmmmomuuppwkf↔,ukffqqpcvhhhyjjfxgjsn¬qpuu scngle
pjrkmetdr into two independent parameters. For our purposes↔,we
ndedftonvejckxyhhuwhnmmpvgqfmmcuwpfkkcvpgnfsqqph icme∧∧jccvbffi??2cufmysckknhq¬¬ss|newtype$
%folio 614 galley 8 (C) Addison-Wesley 1978
W58320---Computer Programming\quad ch. 4\quad f. 614\quad g.
8C

|qleft \6skip {\bf Theorem M} (T. S. Motzkin, 1954). \xskip
{\sl A polynomial chain with m > 0 multiplications has at most
2m degrees of freedom.}
|qleft
 |qleft Proof. \xskip Let $\mu ↓1, \mu ↓2, \ldots , \mu ↓m$ be
the $λ↓i'$s of the chain which correspond to multiplication
operations. Then
$$$\mu ↓i |tab = S↓{2i-1}←4\times S↓{2i},\qquad 1 ≤ i ≤ m,⊗\4skip
\hfill u(x) ⊗= S↓2]βmNβ????4i1,NJ∨(↑↑)2|raiseordrop Nπwhere
each S↓j$ is a certain sum of $\mu$ 's, x's, and $α'$s. Write
$S↓j = T↓j + β↓j,$ where $T↓jf$/usuusu¬mmxf}ε??2.][(sukff????2)][(sqqppws}\≤XIjk??7usuusu¬mmxf??\??2≤≠][))[]'??:44555557Mgq
I≥k(x) Nπis dxvressible as a polynomial in $x, β↓1, \ldots ,
β↓{2m+1}$ with integer coefficients. Since the $β'$? are expressible
asslindajnfkkcvpvmfsmxf}\≤UI17,47[47[47[46, }≤uIu↔, Nπths set
of values represented by all real values of $β↓1,]4. . .←4,λβ↓2←βm↓{+1}λ$conoainfsthssresuwl
ssz offhhsscvquc..HHyjjfxgjshhyjjsujjsiahnmxyh I≤2m + 1 degrees
of freedom)?this can be improved to ??U0}|newtype W58320---Computer
%folio 618 galley 9 (C) Addison-Wesley 1978
Programming\quad ch. 4\quad f. 618\quad g. 9C

|qleft \6skip \quad \xskip It is clear that the results we have
obtained about chains for polynomials in a single variable can
be extended without difficulty to multivariate polynomials.
For example, if we want to find an optimum scmeme for polynomial
evaluation {\sl without} adaptation of coefficients, we can
regard $u(x)$ as a polynomial in the $n + 2$ vjriables $x, u↓n,
\ldots , u↓1, u↓0;$ exercise 38 shows that $n$ multiplications
and $n$ additions are necessary in this case. Indeed, A. Borodcn
[{\sl Theory of Machines and Computations,} ed. by Z. Kohavi
and A. Paz (]dw York: Academic Press, 1971), 45--58] has proved
that Homer's rule (2) is essentially the {\sl only} way to compute
$u(x)$ in $2n$ operations without preconditioning.

With minor variations, the above methods cjknxbssxxzffddfhomcmaunf
invogvcng dcvision, i.e., to rational functions as well as polynomials.
Curiously, the continued-fraction analog of Homer's rule now
turns out to be optimal from an operation-≡ouft stafdvocno,nif
mkqtiplicjzion andndivision speed aje equal, even when preconditioning
is allowed (seesexercise 37).]'??1\quad \xskip ←1!bmetimes division
is hzlpfkwifkkccgnthesevjluationnoffpogynomcaws, evdfnthougm
pvgyxomcuwqsujdsfdfi≡fdfmmvqyicnhzjvxsmxfmkwlppppckwpvmnukffujdkppvm);qwshq¬¬sssefnsx¬¬vpwssmmfhhpisicn
the Shaw--Trakb algorithms for polynomial derivazives. Akothercsx¬¬vlwsiushhyspvgqxmmvuwp}??2XVvN4??44}}M44}¬M44}¬MI6??I6x
?? 1: Since it can be written ($)Fgn↑+!g1 -!41)/(xF4↓≠↓ 1)↔λ$we
can evjwuazesip inn {\sl lllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll??\quad
??\quad ??\quad ??\quad ??\quad ??\quad ??\quad ??\quad ??\quad
??\quad ??\quad ??\quad ??\quad ??\quad ??\quad ??\quad ??\quad
??\quad ??\quad ??\quad ??\quad ??\quad ??\quad ??\quad ??\quad
??\quad ??\quad ??\quad ??\quad ??\quad ??\quad ??\quad ??\quad
??\quad ??\quad}